# -*- coding: utf-8 -*-

"""剑指 Offer II 014. 字符串中的变位词
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

示例 1：
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

示例 2：
输入: s1= "ab" s2 = "eidboaoo"
输出: False

提示：
1 <= s1.length, s2.length <= 10^4
s1 和 s2 仅包含小写字母"""


class Solution:
    """可以用双指针，tail 指针可以消耗掉 s1 中的一个元素时，tail 指针后移一位；否则，head 指针就需要往后移一位，并看所指元素是否需要归还给 s1
    
    看题解，用固定长度的滑动窗口，窗口每往右移动一位，归还一个前导元素，消耗一个尾部元素，这种方案更容易理解"""
    def checkInclusion(self, s1: str, s2: str) -> bool:
        s1_table, yet_count = {}, len(s1)
        for s in s1:
            if s in s1_table.keys():
                s1_table[s] += 1
            else:
                s1_table[s] = 1
        
        head, tail = 0, 0

        try:
            while True:
                if tail < head:
                    tail = head
                if s1_table.get(s2[tail], 0):
                    s1_table[s2[tail]] -= 1
                    yet_count -= 1
                    if yet_count == 0:
                        return True
                    tail += 1
                else:
                    if s2[head] in s1_table.keys():
                        s1_table[s2[head]] += 1
                        yet_count += 1
                    head += 1
        except IndexError:
            return False


if __name__ == '__main__':
    so = Solution()
    print(so.checkInclusion(s1 = "ab", s2 = "eidbaooo"))
    print(so.checkInclusion(s1 = "ab", s2 = "eidboaoo"))

